The present invention relates generally to communications systems, and more specifically to a technique for managing a multiplicity of time-based queues at an output port of a node in a communications network.
A conventional communications system includes a plurality of nodes interconnected by a plurality of data transmission paths to form at least one communications network. The plurality of nodes includes at least one node configurable as an ingress node for originating a data path and at least one node configurable as an egress node for terminating a data path through the network. Each node on the network typically comprises a network switch that can be used to interconnect two or more of the plurality of data paths. Each switch includes at least one input port and at least one output port coupled to respective data paths and is typically configured to allow each output port to receive digital data in the form of, e.g., packets from any input port. The switch determines the appropriate output port for a particular packet by accessing information contained in a header field of the packet.
In the conventional communications system, a Class of Services (CoS) contract is typically formed between an operator of the communications network and a user of the network that specifies the user's parameters for transmitting data over the network. For example, the CoS contract may specify the user's bandwidth for transmitting packets over the network. Further, because each output port of a network switch may receive packets from any input port of the switch, each output port typically includes one or more queues configured to buffer at least one user's packet flow for a particular class of service. The switch typically determines the required class of service for each packet in the flow by accessing information contained in the packet header field.
The network switch typically employs a scheduling algorithm for determining the order in which the packets are to be transmitted from the output port queue(s). For example, each output port may comprise a respective time-sorted queue for each packet flow. Further, the switch may employ a Weighted-Fair Queuing (WFQ) scheduling algorithm operative to determine the order in which the packets are to be transmitted from the time-sorted queues. The WFQ scheduling algorithm may compute a timestamp having a value corresponding to some virtual or actual time for the packet at the head of each queue. Next, the WFQ scheduling algorithm may determine which head-of-line packet has the timestamp with the lowest value, and then select the corresponding queue as the next queue from which to transmit a packet. The WFQ scheduling algorithm allows the switch to set parameters to guarantee the particular class of service for each packet flow.
The network switch may alternatively employ a scheduling algorithm based on a binary tree of comparators to determine the next packet to be transmitted from the output port queue(s). However, like the WFQ scheduling algorithm, the scheduling algorithm based on the binary tree of comparators can typically only be used to manage a limited number of packet flows. For example, a binary tree of N-1 comparators may have log2N levels, in which N is the number of queued flows. Such a tree can become very large and costly to implement as the number of packet flows increases. Further, the time required by such a binary tree of comparators is typically proportional to log2N or worse, which makes this approach unacceptable as N gets large.
Typically, each output port of the switch has a large aggregate “bandwidth” (i.e., the capacity to transfer data per unit of time) and each output line card implements encapsulating the packets into one or more of the various logical and physical data transmission types (e.g., SONET OC-48 POS, SONET OC-3 POS, DS-3, Gigabit Ethernet, SONET OC-48 ATM, etc.). Each output line card may be configured to have a multiplicity of outputs whose aggregate capacity is equal to the capacity of the switch output coming into the card. For example, if the capacity of the switch output is approximately 2.4×109 bits/sec (approximately that of SONET OC-48), then one configuration of an output line card may have four (4) ports of 600×106 bits/sec and another configuration may have sixteen (16) ports of 150×106 bits/sec. Both configurations would make good economic use of the switch output.
Because a number of types of output line cards may be designed, it would be desirable to have as much of the design as possible in common. Specifically, it would be desirable to have the implementation of the WFQ scheduling algorithm be software configurable to handle any combination of packet encapsulation and physical layer types. Further, the enqueuing and dequeuing of packets into the time-sorted queues should be done at a fast enough rate for transferring minimum size packets at full output line data rate capacity using current technology.